package demo1;

import java.util.Scanner;

public class MaxSubarraySum {
    static class Result {
        int sum;
        int start;
        int end;

        Result(int sum, int start, int end) {
            this.sum = sum;
            this.start = start;
            this.end = end;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入元素个数n:");
        int n = scanner.nextInt();
        int[] arr = new int[n];
        System.out.println("请输入" + n + "个整数:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        Result result = findMaxSubarraySum(arr, 0, n - 1);
        System.out.println("最大子段和: " + result.sum);
        System.out.println("起始下标: " + result.start);
        System.out.println("终止下标: " + result.end);
        scanner.close();
    }

    // 分治法求最大子段和，O(nlogn)
    @SuppressWarnings("ClassEscapesDefinedScope")
    public static Result findMaxSubarraySum(int[] arr, int left, int right) {
        if (left == right) {
            int sum = Math.max(0, arr[left]);
            return new Result(sum, left, left);
        }

        int mid = (left + right) / 2;
        Result leftResult = findMaxSubarraySum(arr, left, mid);
        Result rightResult = findMaxSubarraySum(arr, mid + 1, right);
        Result crossResult = findMaxCrossingSubarray(arr, left, mid, right);

        if (leftResult.sum >= rightResult.sum && leftResult.sum >= crossResult.sum) {
            return leftResult;
        } else if (rightResult.sum >= leftResult.sum && rightResult.sum >= crossResult.sum) {
            return rightResult;
        } else {
            return crossResult;
        }
    }

    // 求解跨越中点的最大子段和
    private static Result findMaxCrossingSubarray(int[] arr, int left, int mid, int right) {
        int leftSum = 0, maxLeftSum = 0, leftIndex = mid;
        for (int i = mid; i >= left; i--) {
            leftSum += arr[i];
            if (leftSum > maxLeftSum) {
                maxLeftSum = leftSum;
                leftIndex = i;
            }
        }

        int rightSum = 0, maxRightSum = 0, rightIndex = mid + 1;
        for (int i = mid + 1; i <= right; i++) {
            rightSum += arr[i];
            if (rightSum > maxRightSum) {
                maxRightSum = rightSum;
                rightIndex = i;
            }
        }

        return new Result(maxLeftSum + maxRightSum, leftIndex, rightIndex);
    }
}